﻿//17. 电话号码的字母组合
//给定一个仅包含数字 2 - 9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {
public:
    string s;
    vector<string> board = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };

    void dfs(int index, string& digits, vector<string>& ret)
    {
        if (index == digits.size())
        {
            ret.push_back(s);
            return;
        }
        int z = digits[index] - '0';
        for (int i = 0; i < board[z].size(); i++)
        {
            s.push_back(board[z][i]);
            //递归
            dfs(index + 1, digits, ret);
            //回溯
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits)
    {
        vector<string> ret;
        if (digits.empty())
        {
            return ret;
        }
        dfs(0, digits, ret);
        return ret;
    }
};